package com.zp.self.module.level_4_算法练习.数据结构.链表;

import java.util.LinkedList;

/**
 * @author By ZengPeng
 */
public class 力扣_155_最小栈 {
    //测试
    public static void main(String[] args) {

        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();   //--> 返回 -3.
        minStack.pop();
        minStack.top();      //--> 返回 0.
        System.out.println(minStack.getMin());   //--> 返回 -2.
    }
}
/**
 * 题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 * 分析：
 *      1.直接用现有的linkedList 来做，并用成员变量记录最小值：缺点，pop时可能要重新计算min
 *      #大神的优秀解法 ：创建Node对象，对线中包含当前节点前的最小值。设计相当合理
 * 边界值注意：
 *      1.栈为空，要抛异常哦
 **/
//1.直接用现有的linkedList 来做，并用成员变量记录最小值：缺点，pop时可能要重新计算min
class MinStack {
    LinkedList<Integer> list = new LinkedList<>();
    int min =-1 ;

    public MinStack() {

    }

    public void push(int val) {
        if(list.size()==0) min=val;
        else  min = Math.min(val,min);
        list.add(val);
    }

    public void pop() {
        Integer last = list.removeLast();
        if(last.equals(min)){
            if(list.size()==0) min=-1;
            else {
                min = list.getLast();
                for (Integer integer : list)
                    min = Math.min(min,integer);
            }
        }
    }

    public int top() {
        return list.getLast();
    }

    public int getMin() {
        return min;
    }
}